package num09;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 *
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 *
 * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
 * 示例 1:
 * 输入: nums = [1,2,3,4]
 * 输出: [24,12,8,6]
 * 示例 2:
 * 输入: nums = [-1,1,0,-3,3]
 * 输出: [0,0,9,0,0]
 */
public class Leecode238 {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        //索引右侧的乘积
        int[] rightSum = new int[length];
        //索引左侧的乘积
        int[] leftSum = new int[length];
        //结果集
        int[] answer =  new int[length];
        //当索引i=0时左侧没有数据所以将其初始化为1
        leftSum[0] = 1;
        //索引为最后一位时右边也没有数据所以也初始化为1
        rightSum[length-1] = 1;
        //左边的乘积
        // * 输入: nums = [1,2,3,4]
        // * 输出: [24,12,8,6]
        for (int i = 1; i < length; i++) {
            leftSum[i] = leftSum[i-1]*nums[i-1];
        }
        //左指针数组结果为【1,1,2,6】
        for (int i = length - 2; i >= 0; i--) {
            rightSum[i] = nums[i + 1] * rightSum[i + 1];
        }
        //也可以理解【右边n-1个数的1的乘积，右边n-2个数的乘积，右边n-3个数的乘积】
        //右指针为[24,12,4,1]
        //如果原数组为nums = [1,2,3,4]，初始指针指向nums【0】 -》1 ，那么该指针右边有三个元素，此


        for (int i = 0; i < length; i++) {
            answer[i] = rightSum[i]*leftSum[i];
        }




        return answer;


    }

    public static void main(String[] args) {
        int[] ints = new int[]{1,2,3,4};
        Leecode238 leecode238 = new Leecode238();
        int[] ints1 = leecode238.productExceptSelf(ints);
        for (int i : ints1) {
            System.out.println(i);

        }


    }
}
